#include"red_black_tree.h"
#include<stdio.h>
#include<ctype.h>

int RBTreeEmpty(rb_red_blk_tree *tree){
	return ( tree->root->left == tree->nil);
}

rb_red_blk_node* RBTreeLowest(rb_red_blk_tree *tree){
	rb_red_blk_node* lowest=tree->root->left;
	rb_red_blk_node* nil=tree->nil;
	if( lowest == nil)return NULL;
	
	while( lowest->left != nil){
		lowest=lowest->left;
	}
	return lowest;
}

/*  this file has functions to test a red-black tree of integers */
typedef struct test_t{
	int num;
	int a;
} test_t;

void IntDest(void* a) {
  ;
}

int IntComp(const void* a,const void* b){
  if( ((test_t*)a)->num > ((test_t*)a)->num ) return(1);
  if( ((test_t*)a)->num > ((test_t*)a)->num ) return(-1);
  return(0);
}

void IntPrint(const void* a){
  printf("%i",*(int*)a);
}

void InfoPrint(void* a){
	printf("num=%d,a=%d",((test_t*)a)->num,((test_t*)a)->a);
  ;
}

void InfoDest(void *a){
  free( (test_t*)a);
}

int main() {
  stk_stack* enumResult;
  int option=0;
  int newKey,newKey2;
  test_t *newInfo;
  rb_red_blk_node* newNode;
  rb_red_blk_tree* tree;
  int counter=0;

  tree=RBTreeCreate(IntComp,IntDest,InfoDest,IntPrint,InfoPrint);
  while(option!=9) {
    printf("choose one of the following:\n");
    printf("(1) add to tree\n(2) delete from tree\n(3) query\n");
    printf("(4) find predecessor\n(5) find sucessor\n(6) enumerate\n");
    printf("(7) print tree\n(8) quit\n");
    do option=fgetc(stdin); while(-1 != option && isspace(option));
    option-='0';
    switch(option)
      {
      case 1:
	{
	  printf("type key for new node\n");
	  scanf("%i",&newKey);
	  newInfo=(test_t*) malloc(sizeof(test_t));
	  newInfo->num=newKey;
	  newInfo->a=counter++;
	  RBTreeInsert(tree,&(newInfo->num),newInfo);
	}
	break;
	
      case 2:
	{
	  printf("type key of node to remove\n");
	  scanf("%i",&newKey);
	  if ( ( newNode=RBExactQuery(tree,&newKey ) ) ) RBDelete(tree,newNode);/*assignment*/
	  else printf("key not found in tree, no action taken\n");
	}
	break;

      case 3:
	{
	  printf("type key of node to query for\n");
	  scanf("%i",&newKey);
	  if ( ( newNode = RBExactQuery(tree,&newKey) ) ) {/*assignment*/
	    printf("data found in tree at location %i\n",(int)newNode);
	  } else {
	    printf("data not in tree\n");
	  }
	}
	break;
      case 4:
	{
	  printf("type key of node to find predecessor of\n");
	  scanf("%i",&newKey);
	  if ( ( newNode = RBExactQuery(tree,&newKey) ) ) {/*assignment*/
	    newNode=TreePredecessor(tree,newNode);
	    if(tree->nil == newNode) {
	      printf("there is no predecessor for that node (it is a minimum)\n");
	    } else {
	      printf("predecessor has key %i\n",*(int*)newNode->key);
	    }
	  } else {
	    printf("data not in tree\n");
	  }
	}
	break;
      case 5:
	{
	  printf("type key of node to find successor of\n");
	  scanf("%i",&newKey);
	  if ( (newNode = RBExactQuery(tree,&newKey) ) ) {
	    newNode=TreeSuccessor(tree,newNode);
	    if(tree->nil == newNode) {
	      printf("there is no successor for that node (it is a maximum)\n");
	    } else {
	      printf("successor has key %i\n",*(int*)newNode->key);
	    }
	  } else {
	    printf("data not in tree\n");
	  }
	}
	break;
      /*case 6:
	{
	  printf("type low and high keys to see all keys between them\n");
	  scanf("%i %i",&newKey,&newKey2);
	  enumResult=RBEnumerate(tree,&newKey,&newKey2);	  
	  while ( (newNode = StackPop(enumResult)) ) {
	    tree->PrintKey(newNode->key);
	    printf("\n");
	  }
	  free(enumResult);
	}
	break;*/
	case 6:
	{
	  printf("finding lowest key\n");
		newNode= RBTreeLowest(tree);
		if(!newNode){
			printf("tree is empty\n");
		}
		else{
			printf("lowest is:%d\n",((test_t*)newNode->info)->num);
		}
	 
	}
	break;
   case 7:
	{
	  RBTreePrint(tree);
	}
	break;
    case 8:
	{
	  if( RBTreeEmpty(tree)){ printf("tree is empty\n");}
	  else{printf("tree is not empty\n"); }
	}
	break;	
    /*  case 8:
	{
	  RBTreeDestroy(tree);
	  return 0;
	}
	break;*/
      default:
	printf("Invalid input; Please try again.\n");
      }
  }
  return 0;
}




